/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/longest-common-substring
@Language: C++
@Datetime: 16-02-09 05:57
*/

class Solution {
public:    
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        static const int MAXLEN = 10000;
        int la = A.length();
    	int lb = B.length();
    	int i,j,len=0;
    	int DP[MAXLEN]={0};
    	
    	for(i=0;i<la;++i){
    		for(j=lb-1;j>=0;--j){
    			if (A[i]==B[j]){
    				if (i==0 || j==0)
    					DP[j]=1;
    				else
    					DP[j]=DP[j-1]+1;
    			}
    			else
    				DP[j]=0;			
    			len=(DP[j]>len?DP[j]:len);
    		}
    	}
    	return len;
    }
};
